//Given an integer array nums, handle multiple queries of the following types: 
//
// 
// Update the value of an element in nums. 
// Calculate the sum of the elements of nums between indices left and right 
//inclusive where left <= right. 
// 
//
// Implement the NumArray class: 
//
// 
// NumArray(int[] nums) Initializes the object with the integer array nums. 
// void update(int index, int val) Updates the value of nums[index] to be val. 
// int sumRange(int left, int right) Returns the sum of the elements of nums 
//between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + 
//nums[right]). 
// 
//
// 
// Example 1: 
//
// 
//Input
//["NumArray", "sumRange", "update", "sumRange"]
//[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
//Output
//[null, 9, null, 8]
//
//Explanation
//NumArray numArray = new NumArray([1, 3, 5]);
//numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
//numArray.update(1, 2);   // nums = [1, 2, 5]
//numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 3 * 10⁴ 
// -100 <= nums[i] <= 100 
// 0 <= index < nums.length 
// -100 <= val <= 100 
// 0 <= left <= right < nums.length 
// At most 3 * 10⁴ calls will be made to update and sumRange. 
// 
// Related Topics 设计 树状数组 线段树 数组 👍 309 👎 0

package leetcode.editor.cn;

public class P307RangeSumQueryMutable {
    public static void main(String[] args) {
        NumArray solution = new P307RangeSumQueryMutable().new NumArray(new int[]{1, 3, 5});
        solution.update(0, 1);
        solution.update(1, 2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class NumArray {
        int[] tree;
        int n;

        public NumArray(int[] nums) {
            if (nums.length > 0) {
                n = nums.length;
                tree = new int[n * 2];
                buildTree(nums);
            }
        }

        private void buildTree(int[] nums) {
            for (int i = n, j = 0; i < 2 * n; i++, j++)
                tree[i] = nums[j];
            for (int i = n - 1; i > 0; --i)
                tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }

        void update(int pos, int val) {
            pos += n;
            tree[pos] = val;
            while (pos > 0) {
                int left = pos;
                int right = pos;
                if (pos % 2 == 0) {
                    right = pos + 1;
                } else {
                    left = pos - 1;
                }
                // parent is updated after child is updated
                tree[pos / 2] = tree[left] + tree[right];
                pos /= 2;
            }
        }

        public int sumRange(int l, int r) {
            // get leaf with value 'l'
            l += n;
            // get leaf with value 'r'
            r += n;
            int sum = 0;
            while (l <= r) {
                if ((l % 2) == 1) {
                    sum += tree[l];
                    l++;
                }
                if ((r % 2) == 0) {
                    sum += tree[r];
                    r--;
                }
                l /= 2;
                r /= 2;
            }
            return sum;
        }

       /* int[] arr;
        int size;
        public NumArray(int[] nums) {
            size = nums.length;
            arr = new int[size];
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                arr[i] = sum;
            }
        }
        public int sumRange(int left, int right) {
            if (left == 0) {
                return arr[right];
            }
            return arr[right] - arr[left - 1];
        }
        public void update(int index, int newValue) {
            int oldValue = 0;
            if (index == 0) {
                oldValue = arr[index];
            }else{
                oldValue = arr[index] - arr[index - 1];
            }
            int gap = newValue - oldValue;
            if (gap == 0) {
                return;
            }else{
                for (int i = index; i < size; i++) {
                    arr[i] += gap;
                }
            }

        }*/
    }

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */
//leetcode submit region end(Prohibit modification and deletion)

}